package Week6;

import java.util.PriorityQueue;
import java.util.Scanner;

public class Day36 {
}

//牛客:HJ9 提取不重复的整数
class Main14 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] s = in.next().toCharArray();
        boolean[] hash = new boolean[10];

        for(int i = s.length - 1; i >= 0; i--){
            int x = s[i] - '0';
            if(!hash[x]){
                System.out.print(x);
                hash[x] = true;
            }
        }
    }
}


//牛客:AB32 哈夫曼编码
class Main15 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        PriorityQueue<Long> heap = new PriorityQueue<>();
        while (n-- != 0) {
            long x = in.nextLong();
            heap.offer(x);
        }
// 构建最优⼆叉树 / 构建哈夫曼树
        long ret = 0;
        while (heap.size() > 1) {
            long t1 = heap.poll();
            long t2 = heap.poll();
            heap.offer(t1 + t2);
            ret += t1 + t2;
        }
        System.out.println(ret);
    }
}

//牛客:DP36 abb
class Main16 {
    //动态规划+哈希表
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        char[] s = in.next().toCharArray();

        //模拟哈希表
        //f在更新前表示[0,i-1]区间有多少个 '_x',在更新后表示在[0-i]区间内有多少个'_x'
        //g在更新前表示[0,i-1]区间有多少个 'x',在更新后表示在[0-i]区间内有多少个'x'
        long[] f = new long[26];
        long[] g = new long[26];

        long ret = 0;
        for(int i = 0; i < n; i++){
            int x = s[i] - 'a';
            //记录个数
            ret += f[x];

            //更新
            //在[0-i]区间内有多少个'_x' = [0,i-1]区间有多少个 '_x' + 此时的位置减去前面有多个个x(即前面不是x的个数)
            f[x] = f[x] + i - g[x];
            //在[0-i]区间内有多少个'x' = [0,i-1]区间有多少个 'x' + 1
            g[x] = g[x] + 1;
        }
        System.out.println(ret);
    }
}